package com.cty._04_Optimization._41_StreamMedian;

/**
 * @Auther: cty
 * @Date: 2020/7/16 12:04
 * @Description: 最小堆
 * @version: 1.0
 */
public class MinHeap {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public MinHeap(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return nItems == 0;
    }

    public boolean isFull(){
        return nItems == maxSize;
    }

    public int size(){
        return nItems;
    }

    public void displayHeap(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    public DataItem findMin(){
        if(isEmpty())
            return null;

        return array[0];
    }

    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems] = item;
        trickleUp(nItems++);
        return true;
    }

    public DataItem remove(){
        if(isEmpty())
            return null;

        DataItem temp = array[0];
        array[0] = array[--nItems];
        trickleDown(0);
        return temp;
    }

    private void trickleUp(int index){
        DataItem temp = array[index];
        int parent = (index-1)>>1;

        while(index>0 && temp.getKey()<array[parent].getKey()){
            array[index] = array[parent];
            index = parent;
            parent = (index-1)>>1;
        }
        array[index] = temp;
    }  // end trickleUp()

    private void trickleDown(int index){
        DataItem temp = array[index];
        int smallChild;

        while(index < nItems>>1){
            int leftChild = 2*index + 1;
            int rightChild = leftChild + 1;
            if(rightChild<nItems && array[rightChild].getKey()<array[leftChild].getKey())
                smallChild = rightChild;
            else
                smallChild = leftChild;

            if(temp.getKey() < array[smallChild].getKey())
                break;

            array[index] = array[smallChild];
            index = smallChild;
        }  // end while
        array[index] = temp;
    }  // end trickleDown()

}  // end class
